import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution {
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    //分隔链表
    public ListNode partition(ListNode head, int x) {
        //定义两个虚拟节点，一个拼接
        //定义两个虚拟节点，一个拼接
        ListNode vimNode1 = new ListNode();
        ListNode vimNode2 = new ListNode();
        //遍历链表，大于x的放在vimNode1里，小于x的放入vimNode2里
        ListNode vimNodeMax = vimNode1;
        ListNode vimNodeMin = vimNode2;
        while(head != null) {
            if(head.val >= x) {
                vimNodeMax.next = head;
                vimNodeMax = vimNodeMax.next;
            }else{
                vimNodeMin.next = head;
                vimNodeMin = vimNodeMin.next;
            }
            head = head.next;
        }
        //拼接两个链表
        //vimnode1的最后一个节点的next可能不指向null
        vimNodeMax.next = null;
        vimNodeMin.next = vimNode1.next;
        return vimNode2.next;
    }
    //单词拆分
    public boolean wordBreak(String s, List<String> wordDict) {
        //将单词放入哈希表中方便查找
        Set<String> hash = new HashSet(wordDict);
        int n = s.length();
        //dp[i]表示0-i区间的单词组成字符串在词典中能被查到
        boolean[] dp = new boolean[n+1];
        //拼接空字符，防止越界
        s = " "+s;
        dp[0] = true;
        for(int i = 1; i <= n; i++) {
            //j则是最后一个单词的起始位置
            for(int j = i; j  > 0; j--) {
                //如果可以查到，首先j-1位置的单词可以在字符中找到
                //并且在 j 到 i 位置被包含在字串中
                if(dp[j-1] && hash.contains(s.substring(j,i+1))) {
                    dp[i] = true;
                }
            }
        }
        return dp[n];
    }
}
